package woa.linkedlist;

/**
 * 反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *
 * @author wangpeng
 * @date 2021/11/20
 */
public class ReverseListProblem {

    /**
     * 遍历法
     * 1 -> 2 -> 3 -> 4
     *
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }

        return prev;
    }

    /**
     * 递归法
     *
     * @param head
     * @return
     */
    public static ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = reverseList1(head.next);
        head.next.next = head;
        head.next = null;
        return prev;
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode start = null, end = null;
        ListNode cur = head, prev = null;;
        int i = 1;
        while (cur != null) {
            if (i < left) {
                start = cur;
                cur = cur.next;
            } else if (i <= right) {
                if (i == left) {
                    end = cur;
                }
                ListNode temp = cur.next;
                cur.next = prev;
                prev = cur;
                cur = temp;
            } else {
                break;
            }
            i++;
        }

        if (start != null) {
            start.next = prev;
        }
        if (end != null) {
            end.next = cur;
        }

        return start == null ? prev : head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
//        reverseBetween(head, 1, 2);
        reverseList1(head);
    }
}
